package com.lw.leetcode.dp;

import java.util.Map;
import java.util.TreeMap;

/**
 * 740. 删除并获得点数
 *
 * @Author liw
 * @Date 2021/5/6 13:36
 * @Version 1.0
 */
public class DeleteAndEarn {

    public static void main(String[] args) {
        DeleteAndEarn test = new DeleteAndEarn();
//        int[] arr = {2,2,3,3,3,4};
        int[] arr = {10,8,4,2,1,3,4,8,2,9,10,4,8,5,9,1,5,1,6,8,1,1,6,7,8,9,1,7,6,8,4,5,4,1,5,9,8,6,10,6,4,3,8,4,10,8,8,10,6,4,4,4,9,6,9,10,7,1,5,3,4,4,8,1,1,2,1,4,1,1,4,9,4,7,1,5,1,10,3,5,10,3,10,2,1,10,4,1,1,4,1,2,10,9,7,10,1,2,7,5};
        int i = test.deleteAndEarn(arr);
        System.out.println(i);
    }

    public int deleteAndEarn(int[] nums) {
        Map<Integer, Integer> map = new TreeMap<>();
        for (int num : nums) {
            map.merge(num, 1, (a, b) -> a + b);
        }
        int n1 = 0;
        int n2 = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer key = entry.getKey();
            Integer last = map.get(key - 1);
            if (last == null) {
                n1 = Math.max(n1, n2);
                n2 = n1 + map.get(key) * key;
            } else {
                int item = n1 + key * map.get(key);
                n1 = n2;
                n2 = Math.max(item, n1);
            }
        }
        return Math.max(n1, n2);
    }
}
